#include <stdio.h>
#include <time.h>           
#include <stdlib.h>
#include <string.h>
typedef unsigned char byte_t;
int MAX = 100000;
void gen_rand(int num, int *arr)
{
    int i;
    unsigned long int ran;
    srand(time(NULL));
    for (i = 0; i < num; i++)
    {
        ran = rand() % MAX;
        arr[i] = ran;
     }
}
void print_arr(const int *arr, int num)
{
    int i = 0;
    printf("\n");
    for (; i < num; i++)
    {
        printf("%d\t", arr[i]);
        if (i % 10 == 0)
            printf("\n");
    }
    printf("\n");
}
void sort_arr(int *a, int num)
{
    int i = 0;
    for (; i < num; i++)
    {
        int j = i;
        int min = a[i];
        int pos = i;
        for (; j < num; j++)
        {
            if (a[j] < min)
            {
                pos = j;
                min = a[j];
            }
        }
        if (i != pos)
        {
            int temp = a[i];
            a[i] = a[pos];
            a[pos] = temp;
        }
    }
}
void noexist_normal(int a[], int num)
{
    printf("normal method result:\n");
    int i = 0;
    for (; i < num; i++)
    {
        int bfind = 0;
        int j = 0;
        for (;  j < num; j++)
        {
            if (a[j] == i)
            {
                bfind = 1;
                break;
            }
        }
        if ( bfind == 0)
            printf("%d\t", i);
    }
    printf("\n");
}
void noexist_bitset(int a[], int num)
{
    printf("bitset method result:\n");
    byte_t bitarray[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
    int mem_count = num / 8 + 1;
    unsigned char *bitset = (unsigned char *)malloc(sizeof(char) * mem_count);
    memset(bitset, 0, sizeof(char) * mem_count); 
    int i = 0;
    int last_servel =  num % 8;
    unsigned char *cur_ptr = bitset + num / 8;
    for (; i < 8 - last_servel; i++) //set 1 for last several need't bit 
    {
        *cur_ptr |= bitarray[8 - i - 1];
    }
    i = 0;
    int cur_pos;
    int offset;
    for (; i < num; i++)
    {
        cur_pos = a[i] / 8;
        offset = a[i] % 8;
        cur_ptr = bitset + cur_pos;
        *cur_ptr = *cur_ptr | bitarray[offset];
    }

    i = 0;
    for (; i < mem_count; i++)
    {
        cur_ptr = bitset + i;     
        int j = 0;
        for (; j < 8; j++)
        {
            unsigned char temp = *cur_ptr;
            int cmp_value = temp & bitarray[j];
            if (cmp_value == 0)
                printf("%d\t", i * 8 + j);
        }
    }
    free(bitset);
    printf("\n");
}
int main(int argc, char *argv[])
{
    int a[MAX]; 
    int select  = 0;
    gen_rand(MAX, a);
    printf("input test method,  1 is normal, 2 is bitset:\n");
    scanf("%d", &select);
    if (select == 1)
        noexist_normal(a, MAX);
    else if (select == 2)
        noexist_bitset(a, MAX);
    else printf("error input value\n");

    //print_arr(a, MAX);
    //sort_arr(a, MAX);
    //print_arr(a, MAX);
    //noexist_bitset(a, MAX);
}
